#include "union_find.h"
#include <stdio.h>

UF::UF(int N)
{
    id.reserve(N);
    sz.resize(N,1);
    count = N;
    for(int i = 0;i < N;i++)
    {
        id[i] = i;
    }
}

int UF::getcount() const
{
    return count;
}

void UF::Union(int p, int q)
{
    /*int pid = id[p];
    int qid = id[q];
    for(int i = 0;i < id.capacity();i++)
        if(id[i] == pid)
            id[i] = qid;*/
    int i = root(p);
    int j = root(q);
    if(i == j)
        return;
    if(sz[i] < sz[j])
    {
        id[i] = j;
        sz[j] += sz[i];
    }
    else 
    {
        id[j] = i;
        sz[i] += sz[j];
    }
    count--;
}

bool UF::connected(int p, int q)
{
    //return id[p] == id[q];
    return root(p) == root(q);
}

int UF::root(int i)
{
    while(i != id[i])
    {
        id[i] = id[id[i]];  //路径压缩
        i = id[i];
    }
    return i;
}